import random
import math
# 计算两点之间的欧氏距离
def euclidean_distance(point1, point2):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(point1, point2)))

# 初始化质心
def initialize_centroids(data, k):
    return random.sample(data, k)

def assign_cluster(data, centroids):
    clusters = [[] for _ in range(len(centroids))]  # 初始化k个簇
    for point in data:
        distances = [euclidean_distance(point, centroid) for centroid in centroids]
        closest_centroid = distances.index(min(distances))  # 找到距离最近的质心
        clusters[closest_centroid].append(point)
    return clusters

def update_centroids(clusters):
    new_centroids = []
    for cluster in clusters:
        # 计算簇的均值
        new_centroid = [sum(dim) / len(cluster) for dim in zip(*cluster)]
        new_centroids.append(new_centroid)
    return new_centroids

def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
    # 随机初始化质心
    centroids = initialize_centroids(data, k)
    for i in range(max_iterations):
        # 分配每个点到最近的簇
        clusters = assign_cluster(data, centroids)
        # 更新质心
        new_centroids = update_centroids(clusters)
        # 检查质心是否收敛
        if all(euclidean_distance(centroids[j], new_centroids[j]) < epsilon for j in range(k)):
            print(f"Converged at iteration {i}")
            break
        centroids = new_centroids
    return centroids, clusters
